﻿using System;
using System.Collections.Generic;
using System.Collections;
using SMLib.Base;

namespace MBT.GraphAlgorithms
{

    #region Graph Traversal Step

    // [To DO: Why not using IStateContainer AND ITransition?????]

    /// <summary>
    /// To represent one step in traversing graphs 
    /// assuming that among two nodes, there is not two different edges with the same label
    /// </summary>
    /// <typeparam name="EdgeType"></typeparam>
    /// <typeparam name="NodeType"></typeparam>
    public class GraphTraversalStep<EdgeType, NodeType>
    {
        public EdgeType edgeLabel;
        public NodeType nodeLabel;
        public GraphTraversalStep(EdgeType e, NodeType n)
        {
            if (e == null)
            {
                //int j = 0;
            }
            edgeLabel = e;
            nodeLabel = n;
        }
    }

    /// <summary>
    /// To represent one step in traversing graphs IN NONDETERMINISTIC GRAPHS 
    /// [here, in each non-deterministic step, we also keep other accepted transitions]
    /// </summary>
    /// <typeparam name="EdgeType"></typeparam>
    /// <typeparam name="NodeType"></typeparam>
    public class NDGraphTraversalStep<EdgeType, NodeType>
        : GraphTraversalStep<EdgeType, NodeType>
    {
        bool br;
        bool isBranchStep
        {
            get
            {
                return br;
            }
        }
        List<EdgeType> otherAcceptingEdges;

        public List<EdgeType> OtherAcceptingEdges
        {
            get
            {
                return otherAcceptingEdges;
            }
        }

        public void AddAcceptingEdge(EdgeType e)
        {
            if (br)
            {
                otherAcceptingEdges.Add(e);
            }
            else
                throw new Exception("Other accepting edges could only be defined in Non-deterministic Steps");
        }

        public void MakeItBranch()
        {
            br = true;
            otherAcceptingEdges = new List<EdgeType>();
        }

        public void MakeItNotBranch()
        {
            br = false;
            otherAcceptingEdges = null;
        }

        public NDGraphTraversalStep(EdgeType e, NodeType n, bool branchPoint)
            : base(e, n)
        {
            otherAcceptingEdges = new List<EdgeType>();

            br = branchPoint;
        }

        public override string ToString()
        {
            return this.edgeLabel.ToString();
        }

    }
    #endregion


    /// <summary>
    /// Chineese Postman Problem for directed graphs. It is usd for transition coverage of graph
    /// (Important note: The assumption is that the graph is strongly connected)
    /// <remarks>[the code is adopted based on "The directed Chinese Postman Problem" (by Harold Thimbleby, 2003)]</remarks>
    /// </summary>
    public class DirectedCPP_OLD<STATETYPE, TRANSITIONTYPE>
    {
        //bool finalized;

        /// costs of cheapest arcs OR paths
        float[][] c;
        /// spanning tree of the graph
        int[][] path;
        /// repeated arcs in CPT
        int[][] f;
        /// whether path cost is defined between vertices
        bool[][] defined;
        int[] delta; //deltas of vertices
        public int[] neg, pos;//unbalanced vertices
        int[][] arcs; //adjacency matrix, counts arcs between vertices
        int N;  //number of vertices
        public float basicCost;//sum of all edges

        string[][] cheapestLabel; //labels of cheapest arcs
        List<string>[][] label; //vectors of labels of arcs (for each vertex pair)

        //TranSys graph;
        IDiGraph<STATETYPE, TRANSITIONTYPE> graph;

        /// <summary>
        /// Create a new two dimentional array ([size][size])
        /// </summary>
        /// <typeparam name="T">of type T</typeparam>
        /// <param name="arr"></param>
        /// <param name="size">size of array</param>
        /// <returns></returns>
        T[][] NewTwoDimArray<T>(int size)
        {
            T[][] arr;
            arr = new T[size][];
            for (int i = 0; i < size; i++)
                arr[i] = new T[N];
            return arr;
        }

        /// <summary>
        /// Constructor
        /// </summary>
        /// <param name="graph">the state graph</param>
        public DirectedCPP_OLD(IDiGraph<STATETYPE, TRANSITIONTYPE> graph)
        {
            N = graph.Size;
            init();
            this.graph = graph;
            foreach (STATETYPE sss in graph.GetStates())
            {
                foreach (TRANSITIONTYPE t in graph.TransitionsOf(sss))
                {
                    addArc(t.ToString(), graph.IndexOf(sss), graph.IndexOf(graph.DestinationOf(t)), 1);
                }
            }
            //finalized = true;
        }

        public DirectedCPP_OLD(int N)
        {
            this.N = N;
            //finalized = false;
            init();
        }

        /// <summary>
        /// initialize variables!
        /// </summary>
        void init()
        {
            delta = new int[N];
            defined = NewTwoDimArray<bool>(N);
            c = NewTwoDimArray<float>(N);
            f = NewTwoDimArray<int>(N);
            arcs = NewTwoDimArray<int>(N);
            cheapestLabel = NewTwoDimArray<string>(N);
            path = NewTwoDimArray<int>(N);
            label = NewTwoDimArray<List<string>>(N);
            basicCost = 0;
        }

        /// <summary>
        /// Add an arc to the graph
        /// </summary>
        /// <param name="lab"></param>
        /// <param name="u"></param>
        /// <param name="v"></param>
        /// <param name="cost"></param>
        /// <returns></returns>
        public DirectedCPP_OLD<STATETYPE, TRANSITIONTYPE> addArc(string lab, int u, int v, float cost)
        {
            //if (finalized)
            //    throw new Exception("You cannot add arcs to a finalized graph!");

            //Console.WriteLine("Add edge " + lab + " from " + u + " to " + v);
            if (!defined[u][v])
                label[u][v] = new List<string>();

            //if (lab == null)
            //{
            //    int j = 0;
            //}

            label[u][v].Add(lab);
            basicCost += cost;
            if (!defined[u][v] || c[u][v] > cost)
            {
                c[u][v] = cost;
                cheapestLabel[u][v] = lab;
                defined[u][v] = true;
                path[u][v] = v;
            }
            arcs[u][v]++;
            delta[u]++;
            delta[v]--;
            return this;
        }

        void FindUnbalancedness()
        {
            for (int i = 0; i < N; i++)
            {
                delta[i] += graph.TransitionsOf(graph[i]).Count;
                foreach (TRANSITIONTYPE t in graph.TransitionsOf(graph[i]))
                {
                    for (int j = 0; j < N; j++)
                        if (object.ReferenceEquals(graph.DestinationOf(t), graph[i]))
                        {
                            delta[j]--;
                            break;
                        }
                }
            }
        }

        /// <summary>
        ///  Floyd-Warshall algorithm: Find shortest path between each pairs of nodes
        /// <assumptions>
        /// The graph does't have negative cycles 
        /// </assumptions>
        /// </summary>
        void leastCostPaths()
        {
            for (int k = 0; k < N; k++)
            {
                for (int i = 0; i < N; i++)
                {
                    if (defined[i][k])
                    {
                        for (int j = 0; j < N; j++)
                        {
                            if (defined[k][j]
                                && (!defined[i][j] || (c[i][j] > c[i][k] + c[k][j])))
                            {
                                path[i][j] = path[i][k];
                                c[i][j] = c[i][k] + c[k][j];
                                defined[i][j] = true;
                                if (i == j && c[i][j] < 0) return; //stop on negative cycle
                            }
                        }
                    }
                }
            }
        }

        ///// <summary>
        ///// Check the graph connectivity: The graph should be strongly connected AND it should not have negative cyles
        ///// Essentioaly, we should remove the non-reachable states first!
        ///// </summary>
        //void checkValid()
        //{
        //    for (int i = 0; i < N; i++)
        //    {
        //        for (int j = 0; j < N; j++)
        //            if (!defined[i][j])
        //                throw new Exception("Graph is not strongly connected");

        //        if (c[i][i] < 0)
        //            throw new Exception("Graph has a negative cycle");
        //    }
        //}

        List<int> correspondNodes;
        /// <summary>
        /// 1- We have to remove the nodes in the graph that are not reachable from initial state
        /// 2- We have to add a reset edges to graph to make the graph strongly connected!
        /// By doing this, we try to avoid implementing rural CPP :)))
        /// </summary>
        void MakeGraphValid()
        {
            List<int> NotReachableNodes = new List<int>();
            List<int> NotReachableZers = new List<int>();

            //* Ops! i should be started from 1 not 0! 0 is sometimes not reachable from 0!
            //* Find unreachable nodes (from initial state)
            for (int i = 1; i < N; i++)
            {
                if (!defined[0][i])
                    NotReachableNodes.Add(i);
            }

            //* Find nodes that the initial node is not reachable from them
            for (int i = 0; i < N; i++)
            {
                if (!defined[i][0] && !NotReachableNodes.Contains(i))
                    NotReachableZers.Add(i);
            }


            correspondNodes = new List<int>();

            //* If there was some nodes not reachable from inital node OR the graph (the component) was not strongly connected
            if (NotReachableNodes.Count > 0 || NotReachableZers.Count > 0)
            {
                int currentIndex = 0;
                while (currentIndex < NotReachableZers.Count)
                {
                    //* The node in the current index has
                    bool hasFather = false;
                    for (int i = 0; i < NotReachableZers.Count; i++)
                        if (i == currentIndex)
                            continue;
                        //* If there is node neXt where there is a path from current node to neXt
                        //* We can add "reset" edge to neXt (so, the initial state would be reachable from current node!)
                        else if (defined[NotReachableZers[currentIndex]][NotReachableZers[i]])
                        {
                            hasFather = true;
                            break;
                        }

                    //* There is another node
                    if (hasFather)
                        NotReachableZers.RemoveAt(currentIndex);
                    else
                        currentIndex++;
                }

                //* Add reset nodes
                foreach (int i in NotReachableZers)
                    addArc("Reset", i, 0, 1);

                if (NotReachableNodes.Count > 0)
                {
                    int row = 0, col = 0;
                    for (int i = 0; i < N; i++)
                    {
                        //* Skip the row
                        if (NotReachableNodes.Contains(i))
                            continue;
                        row++;

                        col = 0;
                        for (int j = 0; j < N; j++)
                        {
                            //* Skip the cell in the column
                            if (NotReachableNodes.Contains(j))
                                continue;
                            col++;

                            c[row][col] = c[i][j];
                            path[row][col] = path[i][j];
                            defined[row][col] = defined[i][j];
                            arcs[row][col] = arcs[i][j];
                            cheapestLabel[row][col] = cheapestLabel[i][j];
                            label[row][col] = label[i][j];
                        }
                    }

                    col = 0;
                    for (int i = 0; i < N; i++)
                    {
                        /// Skip the cell in the column
                        if (NotReachableNodes.Contains(i))
                            continue;
                        col++;

                        correspondNodes.Add(i);
                        delta[col] = delta[i];
                    }

                    N -= NotReachableNodes.Count;
                }
                else
                    for (int i = 0; i < N; i++)
                        correspondNodes.Add(i);

                basicCost = 0;

                //* Compute again the basic cost [total of all all edges in the strongly connected component containing the initilal state]
                for (int i = 0; i < N; i++)
                {
                    for (int j = 0; j < N; j++)
                    {
                        if (defined[i][j])
                            basicCost += c[i][j];
                    }
                }
                //* If there was some change, compute least cost AGAIN!
                leastCostPaths();
            }
            else //* If not: No change!
            {
                for (int i = 0; i < N; i++)
                    correspondNodes.Add(i);
            }

        }

        /// <summary>
        /// 
        /// </summary>
        public void findUnbalanced()
        {
            int nn = 0, np = 0;//number of vertices of negative/positive delta
            for (int i = 0; i < N; i++)
                if (delta[i] < 0) nn++;
                else if (delta[i] > 0) np++;
            neg = new int[nn];
            pos = new int[np];
            nn = np = 0;
            for (int i = 0; i < N; i++) //initialise sets
                if (delta[i] < 0) neg[nn++] = i;
                else if (delta[i] > 0) pos[np++] = i;
        }

        //bool isRunable()
        //{

        //}

        /// <summary>
        /// Solve the optimisation problem
        /// <note>
        /// Several other approaches exist (including integer programing, matching, ...)
        /// Cycle canceling [7] can reuse the shortest path results already found, AND we use it because
        /// it is concise. Cycle canceling starts with an approximate solution, then iteratively improves
        /// it. Here, the greedy method is used to establish an initial feasible solution: when the method
        /// terminates, the variable f satisfies the constraints but φ may not yet be optimal.</note>
        /// </summary>
        /// <returns></returns>
        void findFeasible()
        {
            /// Copy delta to local variable
            /// Delete next 3 lines to be faster, but non-reentrant
            int[] delta = new int[N];
            for (int i = 0; i < N; i++)
                delta[i] = this.delta[i];

            for (int u = 0; u < neg.Length; u++)
            {
                int i = neg[u];
                for (int v = 0; v < pos.Length; v++)
                {
                    int j = pos[v];
                    f[i][j] = -delta[i] < delta[j] ? -delta[i] : delta[j];
                    delta[i] += f[i][j];
                    delta[j] -= f[i][j];
                }
            }
        }

        /// <summary>
        /// Cycle canceling uses a residual graph, AND ‘cancels’ negative cycles in it. Theimprovements
        /// method returnstrueinto the whileloop of the solvemethod so it will be invoked repeatedly
        /// while improvements are possible.
        /// </summary>
        /// <returns></returns>
        bool improvements()
        {
            DirectedCPP_OLD<STATETYPE, TRANSITIONTYPE> residual = new DirectedCPP_OLD<STATETYPE, TRANSITIONTYPE>(N);
            for (int u = 0; u < neg.Length; u++)
            {
                int i = neg[u];
                for (int v = 0; v < pos.Length; v++)
                {
                    int j = pos[v];
                    residual.addArc(/*null*/"", i, j, c[i][j]);
                    if (f[i][j] != 0)
                        residual.addArc(/*null*/"", j, i, -c[i][j]);
                }
            }
            residual.leastCostPaths(); //find a negative cycle
            for (int i = 0; i < N; i++)
                if (residual.c[i][i] < 0) //cancel the cycle (if any)
                {
                    int k = 0, u, v;
                    bool kunset = true;
                    u = i;
                    /// find k to cancel
                    do
                    {
                        v = residual.path[u][i];
                        if (residual.c[u][v] < 0 && (kunset || k > f[v][u]))
                        {
                            k = f[v][u];
                            kunset = false;
                        }
                    } while ((u = v) != i);
                    u = i;
                    /// cancel k along the cycle
                    do
                    {
                        v = residual.path[u][i];
                        if (residual.c[u][v] < 0) f[v][u] -= k;
                        else f[u][v] += k;
                    } while ((u = v) != i);
                    /// have another go
                    return true;
                }
            return false; //no improvements found
        }

        public float cost()
        {
            return basicCost + phi();
        }

        protected float phi()
        {
            float phi = 0;
            for (int i = 0; i < N; i++)
                for (int j = 0; j < N; j++)
                    phi += c[i][j] * f[i][j];
            return phi;
        }

        /// anything < 0
        const int NONE = -1;

        /// <summary>
        /// find a path between unbalanced vertices
        /// </summary>
        /// <param name="from"></param>
        /// <param name="f"></param>
        /// <returns></returns>
        int findPath(int from, int[][] f)
        {
            for (int i = 0; i < N; i++)
                if (f[from][i] > 0) return i;
            return NONE;
        }


        public List<NDGraphTraversalStep<string, int>> printCPT(int startVertex)
        {
            List<NDGraphTraversalStep<string, int>> transitionTour
                = new List<NDGraphTraversalStep<string, int>>();

            int v = startVertex;
            /// delete next 7 lines to be faster, but non-reentrant

            int[][] arcs = NewTwoDimArray<int>(N);

            int[][] f = NewTwoDimArray<int>(N);
            for (int i = 0; i < N; i++)
                for (int j = 0; j < N; j++)
                {
                    arcs[i][j] = this.arcs[i][j];
                    f[i][j] = this.f[i][j];
                }

            //transitionTour.Add(startVertex);

            while (true)
            {
                int u = v;
                if ((v = findPath(u, f)) != NONE)
                {
                    f[u][v]--; //remove path
                    for (int p; u != v; u = p)//break down path into its arcs
                    {
                        p = path[u][v];

                        transitionTour.Add(new NDGraphTraversalStep<string, int>(cheapestLabel[u][p], p, false));
                        //Console.WriteLine("Take arc " + cheapestLabel[u][p] + " from " + u + " to " + p);
                    }
                }
                else
                {
                    int bridgeVertex = path[u][startVertex];
                    if (arcs[u][bridgeVertex] == 0)
                        break; //finished if bridge already used
                    v = bridgeVertex;
                    for (int i = 0; i < N; i++)//find an unused arc, using bridge last
                        if (i != bridgeVertex && arcs[u][i] > 0)
                        {
                            v = i;
                            break;
                        }
                    arcs[u][v]--; //decrement count of parallel arcs
                    transitionTour.Add(new NDGraphTraversalStep<string, int>(label[u][v][(arcs[u][v])], v, false));
                    //Console.WriteLine("Take arc " + label[u][v][(arcs[u][v])] + " from " + u + " to " + v); //use each arc label in turn
                }
            }

            /// If the graph was different from the original one, replace graph indecis
            foreach (NDGraphTraversalStep<string, int> node in transitionTour)
            {
                node.nodeLabel = correspondNodes[node.nodeLabel];
            }
            return transitionTour;
        }

        /// <summary>
        /// 
        /// </summary>
        public void solve()
        {
            leastCostPaths();

            //checkValid();
            MakeGraphValid();

            findUnbalanced();
            findFeasible();

            //* TODO!
            //* while (improvements()) ;
        }
    }


    ///// <summary>
    ///// Chineese Postman problem for directed graph AND open path (where the postman is not required to return to the initial state)
    ///// </summary>
    //class Open_DirectedCPP
    //{
    //    class Arc
    //    {
    //        public string lab;
    //        public int u, v;
    //        public float cost;

    //        public Arc(string lab, int u, int v, float cost)
    //        {
    //            this.lab = lab;
    //            this.u = u;
    //            this.v = v;
    //            this.cost = cost;
    //        }
    //    }

    //    List<Arc> arcs = new List<Arc>();
    //    int N;

    //    public Open_DirectedCPP(int vertices)
    //    {
    //        N = vertices;
    //    }

    //    Open_DirectedCPP addArc(string lab, int u, int v, float cost)
    //    {
    //        if (cost < 0) throw new Exception("Graph has negative costs");
    //        arcs.Add(new Arc(lab, u, v, cost));
    //        return this;
    //    }

    //    float printCPT(int startVertex)
    //    {
    //        DirectedCPP bestGraph = null, g;
    //        float bestCost = 0, cost;
    //        int i = 0;
    //        do
    //        {
    //            g = new DirectedCPP(N + 1);
    //            for (int j = 0; j < arcs.Count; j++)
    //            {
    //                Arc it = (Arc)arcs[j];
    //                g.addArc(it.lab, it.u, it.v, it.cost);
    //            }
    //            cost = g.basicCost;
    //            g.findUnbalanced(); //initialise g.neg on original graph
    //            g.addArc("'virtual star'", N, startVertex, cost);
    //            g.addArc("'virtual end'",
    //                //graph is Eulerian if neg.length=0
    //            g.neg.Length == 0 ? startVertex : g.neg[i], N, cost);
    //            g.solve();
    //            if (bestGraph == null || bestCost > g.cost())
    //            {
    //                bestCost = g.cost();
    //                bestGraph = g;
    //            }
    //        } while (++i < g.neg.Length);
    //        //System.out.println("Open CPT from "+startVertex+" (ignore virtual arcs)");
    //        bestGraph.printCPT(N);
    //        return cost + bestGraph.phi();
    //    }
    //}

    ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    /// <summary>
    /// 
    /// </summary>
    public interface ICostDefenition<STATETYPE, TRANSITIONTYPE>
    {
        /// <summary>
        /// Cost definer
        /// </summary>
        /// <param name="t"></param>
        /// <returns></returns>
        float CostOfTransition(TRANSITIONTYPE t, STATETYPE s);
    }

    /// <summary>
    /// Interface to define cost AND probability for each transition
    /// [This can also be defined in defenition of transitions!]
    /// </summary>
    public interface ICostProbDefinition<STATETYPE, TRANSITIONTYPE> : ICostDefenition<STATETYPE, TRANSITIONTYPE>
    {
        /// <summary>
        /// Probability definer
        /// </summary>
        /// <param name="t"></param>
        /// <returns></returns>
        float ProbOfTransition(TRANSITIONTYPE t, STATETYPE s);
    }



}
